﻿#include <stdio.h>
#include <stdlib.h>
#include <iostream>

#define MaxTreeSize 10;
typedef char TElemType;
typedef struct BiTNode {
    TElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void InitTree(BiTree &BT) {
    BT = NULL;
}

void CreateTree(BiTree &BT) {
    TElemType e;
    std::cin >> e;
    if (e == '#')
        e = NULL;
    else {
        BT = (BiTNode *) malloc(sizeof(BiTNode));
        BT->data = e;
        CreateTree(BT->lchild);
        CreateTree(BT->rchild);
    }
}


/*
 * 假设二叉树采用二叉链表存储结构存储，设计一个算法，求先序遍历序列中第k（1<=k<=树中结点个数）个结点的值
 * 操作步骤：设置一个全局变量i（处置为1）来表示先序遍历时，当前访问的是第几个结点。
 *          当二叉树为空时，返回特殊字符'#'；当k==i时，返回BT—>data;当k！=i时，递归地在左子树中查找，若找到返回，若没找到则递归的在右子树中查找，并返回其结果。
 */
int i = 1;

TElemType BiTNode_k_Value(BiTree BT, int k) {
    if (BT == NULL)
        return '#';
    if (i == k)
        return BT->data;
    i++;
    TElemType ch;
    ch = BiTNode_k_Value(BT->lchild, k);
    if (ch != '#')
        return ch;
    ch = BiTNode_k_Value(BT->rchild, k);
    return ch;
}

int main() {
    BiTree BT;
    InitTree(BT);
    std::cout << "请按照先序序列输入树结点创建一棵二叉树（'#'表示空）：\n";
    CreateTree(BT);

    int k;
    std::cout << "请输入要查找先序序列中第几个元素的值：";
    std::cin >> k;
    TElemType value = BiTNode_k_Value(BT, k);
    std::cout << "先序序列中第" << k << "个元素的值为：" << value;

    return 0;
}